import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.util.Vector;

/**
 * @version Create on 2012-10-29
 * @author Yinzi Chen
 */

public class FourSum {

	public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
		Arrays.sort(num);
		int n = num.length;
		HashMap<Integer, Vector<String>> map = new HashMap<Integer, Vector<String>>();
		for (int i = n - 1; i >= 0; --i) {
			for (int j = i + 1; j < n; ++j) {
				Vector<String> vec = map.get(num[i] + num[j]);
				String s = i + "," + j;
				if (vec == null) {
					vec = new Vector<String>();
					vec.add(s);
					map.put(num[i] + num[j], vec);
				} else {
					vec.add(s);
				}
				while (j + 1 < n && num[j + 1] == num[j])
					j++;
			}
			if (i - 1 >= 0 && num[i - 1] == num[i]) {
				Vector<String> vec = map.get(num[i - 1] + num[i]);
				String s = (i - 1) + "," + i;
				if (vec == null) {
					vec = new Vector<String>();
					vec.add(s);
					map.put(num[i - 1] + num[i], vec);
				} else {
					vec.add(s);
				}
			}
			while (i - 1 >= 0 && num[i - 1] == num[i])
				i--;
		}
		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
		StringTokenizer st;
		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) {
				Vector<String> vec = map.get(target - num[i] - num[j]);
				if (vec != null) {
					for (String s : vec) {
						st = new StringTokenizer(s, ",");
						int p = Integer.parseInt(st.nextToken()), q = Integer
								.parseInt(st.nextToken());
						if (p <= j)
							break;
						ArrayList<Integer> list = new ArrayList<Integer>();
						list.add(num[i]);
						list.add(num[j]);
						list.add(num[p]);
						list.add(num[q]);
						res.add(list);
					}
				}
				while (j + 1 < n && num[j + 1] == num[j])
					j++;
			}
			while (i + 1 < n && num[i + 1] == num[i])
				i++;
		}
		return res;
	}

	public static void main(String[] args) {
		FourSum a = new FourSum();
		a.fourSum(new int[] { 0, 0, 0, 0 }, 0);
	}

}
